package j2024.j202409;

import java.util.Arrays;

public class j0909 {
    /**
     * 409. 最长回文串
     * @param s
     * @return
     */
    public int longestPalindrome(String s) {
        int[] hash = new int[127];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i)]++;
        }
        int ret = 0;
        for(int x:hash){
            ret+=x/2*2;
        }
        if(ret<s.length()){
            ret++;
        }
        return ret;
    }

    /**
     * 942. 增减字符串匹配
     * @param s
     * @return
     */
    public int[] diStringMatch(String s) {
        int n = s.length();
        int len = n+1;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = i;
        }
        int[] ret = new int[len];
        int left = 0,right = len-1;
        for (int i = 0; i < n; i++) {
            if(s.charAt(i)=='I'){
                ret[i] = arr[left++];
            }else {
                ret[i] = arr[right--];
            }
        }
        ret[len] = arr[left];
        return ret;
    }

    /**
     * 455. 分发饼干
     * @param g
     * @param s
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int ng = g.length,ns = s.length;
        int i = 0,j = 0;
        int count = 0;
        while(i<ng && j<ns){
            if(s[j]>=g[i]){
                j++;i++;
                count++;
            }else {
                j++;
            }
        }
        return count;
    }

    /**
     * 553. 最优除法
     * @param nums
     * @return
     */
    public String optimalDivision(int[] nums) {
        int n = nums.length;
        StringBuilder ret = new StringBuilder();
        ret.append(nums[0]);
        if(n==1){
            return ret.toString();
        }
        if(n==2){
            ret.append("/").append(nums[1]);
            return ret.toString();
        }
        ret.append("/").append("(").append(nums[1]);
        for (int i = 2; i < n; i++) {
            ret.append("/").append(nums[i]);
        }
        ret.append(")");
        return ret.toString();
    }

    /**
     * 45. 跳跃游戏 II
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int ret = 0,left = 0,right = 0,maxPos = 0,n = nums.length;
        while(left<=right){
            if(maxPos>=n-1){
                return ret;
            }
            for (int i = left; i <= right; i++) {
                maxPos = Math.max(nums[i]+i,maxPos);
            }
            left = right+1;
            right=maxPos;
            ret++;

        }
        return ret;
    }
    public static int jump2(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]+j>=i){
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        jump2(nums);
    }
}
